import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import javax.swing.event.ListSelectionEvent;

/*
 * @lc app=leetcode.cn id=315 lang=java
 *
 * [315] 计算右侧小于当前元素的个数
 *
 * https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/description/
 *
 * algorithms
 * Hard (36.56%)
 * Likes:    120
 * Dislikes: 0
 * Total Accepted:    8.4K
 * Total Submissions: 22.8K
 * Testcase Example:  '[5,2,6,1]'
 *
 * 给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于
 * nums[i] 的元素的数量。
 *
 * 示例:
 *
 * 输入: [5,2,6,1]
 * 输出: [2,1,1,0]
 * 解释:
 * 5 的右侧有 2 个更小的元素 (2 和 1).
 * 2 的右侧仅有 1 个更小的元素 (1).
 * 6 的右侧有 1 个更小的元素 (1).
 * 1 的右侧有 0 个更小的元素.
 *
 *
 */

// @lc code=start
class Solution {
    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        if(n == 0) return new ArrayList<>();
        int[] dp = new int[n];
        dp[n-1] = 0;
        for(int i=n-2 ;i > -1;i--)
            if(nums[i] > nums[i+1])
                dp[i] = dp[i+1] + 1;
            else {
                int index = i+2;
                while(index < n && nums[i] < nums[index]) {
                    index++;
                }
                if (index == n) {
                    dp[i] = 0;
                } else {
                    dp[i] = dp[index] + 1;
                }

            }
        List<Integer> list = new ArrayList<>();
        for(int a : dp)
            list.add(a);
        return list;
    }
}
// @lc code=end

